
/*
VectorHeap.java
Autor: Luis Antonio Sigüenza Leiva
Carné: 10297
Fecha: 22 de septiembre del 2011
 * Descripcion: clase que crea un vector-heap
*/


import java.util.Vector;

public class VectorHeap<E extends Comparable<E>> implements Heap <E>{
    
   //******************************************************************
    //REFERENCIA DE CLASE TOMADA DEL LIBRO:
    //1.- Java Structures: Data Structures for the Principled Programmer
    //Capitulo 12: Arboles binarios
    //2.- Colas con prioridad en Java: Implementacion con Vector y Heaps
    //Autor:  Carlos López Camey
    //****************************************************************** 
   
    //Atributos de clase
    protected Vector<E> data; 

    //Método constructor (predefinido) crea una nueva cola de prioridad vacia.
    public VectorHeap(){
        data = new Vector<E>();
    }
   
    //Método que devuelve el indice del padre
    protected static int parent(int i){
        return (i-1)/2;
    }
    
    //Método que devuelve el indice del hijo izquierdo
    protected static int left(int i){
    return 2*i+1;
    }
    
    //Método que devuelve el indice del hijo derecho
    protected static int right(int i){
    return 2*(i+1);
    }

    //Método que mueve al hijo (izquierdo) a una nueva posicion de acuerdo
    // a la prioridad del mismo
    protected void percolateUp(int leaf){
    int parent = parent(leaf);
    E value = data.get(leaf);
    while (leaf > 0 && (value.compareTo(data.get(parent)) < 0))
        {
         data.set(leaf,data.get(parent));
         leaf = parent;
         parent = parent(leaf);
        }
    data.set(leaf,value);
    }
    
    //Metodo que retorna el primer elemento de la cola
    public E getFirst() {
        return data.get(0);
    }

    //Metodo que devuelve el elemento con mayor prioridad
    @Override
    public E peek() {
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        return minVal;
    }
    
    //Método que agrega un valor a la cola y lo ordena de acuerdo a su 
    //prioridad
    public void add(E value){
        data.add(value);
        percolateUp(data.size()-1);
    }

    //Metodo que devuelve el tamaño de la cola
    public int size() {
        int tamano = data.size();
        return tamano;
    }

}
